package io.tec.cloud.algorithm.c09_v20220711;

import java.util.ArrayList;

/**
 * 53：53	09_2	09	2	09排序总结、链表相关面试题	数个数或者快慢指针4个练习题
 * <p>
 * 数个数或者快慢指针4个练习题
 * 1）输入链表头节点，奇数长度返回中点，偶数长度返回上中点
 * <p>
 * 2）输入链表头节点，奇数长度返回中点，偶数长度返回下中点
 * <p>
 * 3）输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
 * <p>
 * 4）输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
 */
public class Code09_2_LinkedListMid {

    static class Node<V> {
        V value;

        Node next;

        public Node(V v) {
            this.value = v;
        }
    }

    /**
     * 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
     * @param head
     * @return
     */
    public static Node midOrUpMidNode1(Node head) {
        int size = 0;
        Node cur = head;
        while (cur != null) {
            size++;
            cur = cur.next;
        }
        // 原始数据
        // 如果是奇数，size = 5；目标 mid = 3；算法 5 / 2 = 2 【x】;
        // 如果是偶数，size = 6；目标 mid = 3；算法 6 / 2 = 3 【√】;

        // 新算法
        // (size + 1) / 2
        // 如果是奇数，size = 5；mid = 3； 6 / 2 = 3 【√】;
        // 如果是偶数，size = 6；mid = 3； 7 / 2 = 3 【√】;
        int mid = (size + 1) / 2;
        cur = head;
        // TODO head 是第一个点，所以mid要先减一个
        mid --;
        while (mid > 0) {
            cur = cur.next;
            mid--;
        }
        return cur;
    }

    /**
     * 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
     * @param head
     * @return
     */
    public static Node midOrUpMidNode2(Node head) {
        Node fast = head;
        Node slow = head;

        if (fast.next == null) {
            return head;
        }

        if (fast.next.next == null) {
            return fast;
        }

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        fast = head;
        while (slow.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

    public static Node midOrUpMidNode3(Node head) {
        Node fast = head;
        Node slow = head;

        if (fast.next == null || fast.next.next == null) {
            return head;
        }
        fast = fast.next.next;
        slow = slow.next;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }


    /**
     * 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
     * @param head
     * @return
     */
    public static Node midOrDownMidNode1(Node head) {

        int size = 0;
        Node cur = head;
        while (cur != null) {
            size++;
            cur = cur.next;
        }


        // 原始数据
        // 如果是奇数，size = 5；目标 mid = 3；算法 5 / 2 = 2 【x】;
        // 如果是偶数，size = 6；目标 mid = 4；算法 6 / 2 = 3 【x】;

        // 新算法
        // size / 2 + 1
        // 如果是奇数，size = 5；mid = 3； 6 / 2 = 3 【√】;
        // 如果是偶数，size = 6；mid = 3； 7 / 2 = 3 【√】;
        int mid = size / 2 + 1;
        cur = head;
        mid--;
        while (mid > 0) {
            cur = cur.next;
            mid--;
        }
        return cur;
    }

    /**
     * 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
     * @param head
     * @return
     */
    public static Node midOrDownMidNode2(Node head) {
        Node fast = head;
        Node slow = head;

        if (fast.next == null) {
            return head;
        }

        if (fast.next.next == null) {
            return fast;
        }

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
     * @param head
     * @return
     */
    public static Node midOrDownMidNode3(Node head) {
        Node fast = head;
        Node slow = head;

        if (fast.next == null) {
            return head;
        }

        if (fast.next.next == null) {
            return fast;
        }

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
     * @param head
     * @return
     */
    public static Node midOrUpMidPreNode(Node head) {
        int size = 0;
        Node cur = head;
        while (cur != null) {
            size++;
            cur = cur.next;
        }
        int mid = (size -1) / 2;
        cur = head;
        mid --;
        while (mid > 0) {
            cur = cur.next;
            mid--;
        }
        return cur;
    }

//    public static Node midOrUpMidPreNode2(Node head) {
//
//    }
//
//    /**
//     * 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
//     * @param head
//     * @return
//     */
//    public static Node midOrDownMidPreNode(Node head) {
//
//    }

    public static Node right1(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        ArrayList<Node> arr = new ArrayList<>();
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get((arr.size() - 1) / 2);
    }

    public static Node right2(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        ArrayList<Node> arr = new ArrayList<>();
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get(arr.size() / 2);
    }



    public static void main(String[] args) {
        Node test = null;
        test = new Node(0);
        test.next = new Node(1);
        test.next.next = new Node(2);
        test.next.next.next = new Node(3);
        test.next.next.next.next = new Node(4);
        test.next.next.next.next.next = new Node(5);
        test.next.next.next.next.next.next = new Node(6);
        test.next.next.next.next.next.next.next = new Node(7);
        test.next.next.next.next.next.next.next.next = new Node(8);

        Node ans1 = null;
        Node ans2 = null;
        Node ans3 = null;
        Node ans4 = null;

//        ans1 = midOrUpMidNode1(test);
//        ans2 = midOrUpMidNode2(test);
//        ans4 = midOrUpMidNode3(test);
//        ans3 = right1(test);
//        System.out.println(ans1 != null ? ans1.value : "无");
//        System.out.println(ans2 != null ? ans2.value : "无");
//        System.out.println(ans3 != null ? ans3.value : "无");
//        System.out.println(ans4 != null ? ans4.value : "无");

        ans1 = midOrDownMidNode1(test);
        ans2 = midOrDownMidNode2(test);
        ans4 = midOrDownMidNode3(test);
        ans3 = right2(test);
        System.out.println(ans1 != null ? ans1.value : "无");
        System.out.println(ans2 != null ? ans2.value : "无");
        System.out.println(ans3 != null ? ans3.value : "无");
        System.out.println(ans4 != null ? ans4.value : "无");
//
//        ans1 = midOrUpMidPreNode(test);
//        ans2 = right3(test);
//        System.out.println(ans1 != null ? ans1.value : "无");
//        System.out.println(ans2 != null ? ans2.value : "无");
//
//        ans1 = midOrDownMidPreNode(test);
//        ans2 = right4(test);
//        System.out.println(ans1 != null ? ans1.value : "无");
//        System.out.println(ans2 != null ? ans2.value : "无");

    }


}
